import random
from collections import defaultdict


class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        counter = defaultdict(int)
        for c in word:
            counter[c] += 1
        values = list(sorted(counter.values()))
        # 枚举每一位，包括这位及其之前全部删除 后续删除到diff
        ans = float('inf')
        for i in range(len(values)):
            cnt = 0
            for j in range(len(values)):
                if j < i:
                    cnt += values[j]
                else:
                    if values[j] - values[i] > k:
                        cut = values[j] - values[i] - k
                        cnt += cut
            ans = min(cnt, ans)
        return ans

    def exhaustSearch(self, word, k):
        global min_step
        min_step = float('inf')

        def dfs(i, step, counter):
            global min_step
            if i == len(word):
                c = list(filter(lambda x: x > 0, counter.values()))
                for ii in range(len(c)):
                    for jj in range(len(c)):
                        if abs(c[ii] - c[jj]) > k:
                            return
                min_step = min(min_step, step)
                return
            counter[word[i]] += 1
            dfs(i + 1, step, counter)
            counter[word[i]] -= 1
            dfs(i + 1, step + 1, counter)

        dfs(0, 0, defaultdict(int))
        return min_step


def generate():
    word_bet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    n = random.randint(1, 10)
    word = ''.join(random.choices(word_bet, k=n))
    k = random.randint(0, n)
    return word, k


if __name__ == '__main__':
    s = Solution()
    if 1:
        for t in range(10000):
            word, k = generate()
            r1 = s.exhaustSearch(word, k)
            r2 = s.minimumDeletions(word, k)
            if r1 == r2:
                continue
            else:
                print(word, k)
                print(f"dfs={r1},simulation={r2}")
    r1 = s.minimumDeletions('XBWKXHRBRK', 0)
